Simulation-based techniques are one of the instruments for testing a computing system. The system under test, usually in the form of software or program code, is executed on simulated environments to verify whether the system generates the expected results. Verification is typically done by analyzing the test results generated in simulated environments.
A main concern inherent to verification by simulation is proper test coverage (i.e., whether all or at least the most important aspects of the system are covered by the test model). Test planning techniques are used to try to focus on target coverage areas by preventing omissions in testing, before the tests are implemented and executed. One technique involves narrowing down a large test space.
To minimize the risk of narrowing down the test space too much (i.e., to a point that certain bugs in the software may escape the test scope), test planning techniques may be used that require modeling of the test space as a functional coverage model. Functional coverage focuses on the functionality of the system under test, and is used to check that every aspect of the system's functionality is tested.
Functional coverage may be used to measure the extent to which testing covers program capabilities and is implementation specific. As a result, a functional coverage model is generally difficult to design, due to the variety of factors (e.g., inputs, scenarios, configurations, the application's internal state, etc.) that may have to be taken into consideration.
Traditionally, a functional coverage model includes a set of variables (i.e., attributes), the respective values of the variables, and restrictions on their value combinations. The restrictions are Boolean expressions defining when value combinations are valid or invalid. The set of valid value combinations (i.e. all combinations from the product of the values that pass the restrictions) defines the space to be tested. Such combinatorial modeling of the test space usually requires manual effort.
In a combinatorial test design, a subset of the test space is selected so that it covers all possible combinations of n number of variables. The required coverage of the selected subset is referred to as interaction level (i.e., interaction level 2 means that for every two variables, all valid value combinations must appear in the selected subset of the test space)—the motivation for this approach is that statistics show that most bugs depend on the interaction between a small number of variables.
One of the problems encountered by modeling tools is the scalability issue. The size of the model is the product of the number of values for each attribute, and grows exponentially with the number of attributes. The number of restrictions also tends to grow rapidly when one needs to express complex relations between attributes. The required amount of manual effort, computation time, as well as the size of the inner representation of the model, may grow as the number of restrictions grows. Thus, for some models, it is practically impossible to express even relatively simple relations between attributes.